package cn.bellychang.leetcode.question051;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ChangLiang
 * @date 2021/3/20
 */
public class Solution {

    public List<List<String>> solveNQueens(int n) {

        List<List<String>> result = new ArrayList<>();

        /**
         * 下标表示行 值表示queen存储在哪一列
         */
        int[] tempResult = new int[n];
        for (int i = 0; i < tempResult.length; i++) {
            tempResult[i] = -1;
        }

        solveNQueens(n, 0, result, tempResult);
        return result;
    }

    private void solveNQueens(int n, int currRow, List<List<String>> result, int[] tempResult){
        if (n == currRow) {
            result.add(convertTempResultToList(tempResult, n));
        }
        for (int column = 0; column < n; column++) {
            if (isOk(n, currRow, column, tempResult)) {
                // 这一步实现了solution.pop(case)的功能 实现了覆盖写
                tempResult[currRow] = column;
                solveNQueens(n, currRow + 1, result, tempResult);
            }
        }
    }

    private List<String> convertTempResultToList(int[] tempResult, int n) {

        List<String> result = new ArrayList<>();

        char[] chars = new char[n];
        for (int i = 0; i < chars.length; i++) {
            chars[i] = '.';
        }
        for (int i = 0; i < tempResult.length; i++) {
            String str = new String(chars);
            char[] chars1 = str.toCharArray();
            chars1[tempResult[i]] = 'Q';
            result.add(new String(chars1));
        }
        return result;
    }

    private boolean isOk(int n, int currRow, int currColumn, int[] result) {
        int leftUpColumn = currColumn - 1;
        int rightUpColumn = currColumn + 1;
        for (int i = currRow - 1; i >= 0; i--) {

            // 注意result的含义 下标表示行 值表示queen存储在哪一列

            // result=[0,2,-1,-1]
            //         0 1  2  3
            // 当处理row=2时 column=0,1,2,3  要看第1行 0,1,2,3是否有存储 存储的值就是列的index

            // 第i行的column列有棋子吗
            if (result[i] == currColumn) {
                return false;
            }

            if (leftUpColumn >= 0) {
                // 考察左对角线 第i行 leftUp列有棋子吗
                if (result[i] == leftUpColumn) {
                    return false;
                }
            }

            if (rightUpColumn < n) {
                // 考察右对角线 第i行 rightUpColumn有棋子吗
                if (result[i] == rightUpColumn) {
                    return false;
                }
            }

            leftUpColumn--;
            rightUpColumn++;
        }
        return true;
    }
}
